#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

template <typename Iterator>
Iterator kth_element(Iterator first,Iterator median,Iterator last){
	if (first == last || first + 1 == last)
		return first;
	if (median < first || median > last)
		return last;
}
template <typename T>
T __median_of_3(T a ,T b ,T c){
	if (a <= b ){
		if (b <= c)
			return b;
		else if (a <= c)
			return c;
		else 
			return a;
	}
	else {
		if (c <= b)
			return b;
		if (a <= c)
			return a;
		else 
			return c;
	}
}
template <typename Iterator>
Iterator __ungarded_partition(Iterator first,Iterator last){
	typedef typename std::iterator_traits<Iterator>::value_type value_t;
	value_t pivot = __median_of_3(*first,*(last-1),*(first + (last - first)/2));
	while (true){
		while (*first < pivot) ++first;
		--last;
		while (pivot < *last) --last;
		if (!(first < last)) return first;
		std::iter_swap(first,last);
		++first;
	}
}

template <typename Iterator>
void ___insertion_sort(Iterator first,Iterator last){
	for (Iterator i = first + 1; i != last; ++i){
		typedef typename std::iterator_traits<Iterator>::value_type value_t;
		value_t value = *i;
		Iterator next = i;
		Iterator follow = i;
		--next;
		while (value < *next){
			*follow = *next;
			follow = next;
			if (next == first)
				break;
			--next;
		}
		*follow = value; 
	}
}
